Parallel searching on m rays☆☆This research is supported by the DFG-Project “Diskrete Probleme”, No. Ot 64/8-3.

AbstractWe investigate parallel searching on m concurrent rays. We assume that a target t is located somewhere on one of the rays; we are given a group of m point robots each of which has to reach t. Furthermore, we assume that the robots have no way of communicating over distance. Given a strategy S we are interested in the competitive ratio defined as the ratio of the time needed by the robots to reach t using S and the time needed to reach t if the location of t is known in advance.If a lower bound on the distance to the target is known, then there is a simple strategy which achieves a competitive ratio of 9—independent of m. We show that 9 is a lower bound on the competitive ratio for two large classes of strategies if m⩾2.If the minimum distance to the target is not known in advance, we show a lower bound on the competitive ratio of 1+2(k+1)k+1/kk where k=⌈logm⌉ where log is used to denote the base-2 logarithm. We also give a strategy that obtains this ratio